package com.mango.leet.code.week1.game283;

import java.util.*;
/**
 * 6019. 替换数组中的非互质数
 */
/**
 * 给你一个整数数组 nums 。请你对数组执行下述操作：
 *
 * 从 nums 中找出 任意 两个 相邻 的 非互质 数。
 * 如果不存在这样的数，终止 这一过程。
 * 否则，删除这两个数，并 替换 为它们的 最小公倍数（Least Common Multiple，LCM）。
 * 只要还能找出两个相邻的非互质数就继续 重复 这一过程。
 * 返回修改后得到的 最终 数组。可以证明的是，以 任意 顺序替换相邻的非互质数都可以得到相同的结果。
 *
 * 生成的测试用例可以保证最终数组中的值 小于或者等于 108 。
 *
 * 两个数字 x 和 y 满足 非互质数 的条件是：GCD(x, y) > 1 ，其中 GCD(x, y) 是 x 和 y 的 最大公约数 。
 *
 *
 *
 * 示例 1 ：
 *
 * 输入：nums = [6,4,3,2,7,6,2]
 * 输出：[12,7,6]
 * 解释：
 * - (6, 4) 是一组非互质数，且 LCM(6, 4) = 12 。得到 nums = [12,3,2,7,6,2] 。
 * - (12, 3) 是一组非互质数，且 LCM(12, 3) = 12 。得到 nums = [12,2,7,6,2] 。
 * - (12, 2) 是一组非互质数，且 LCM(12, 2) = 12 。得到 nums = [12,7,6,2] 。
 * - (6, 2) 是一组非互质数，且 LCM(6, 2) = 6 。得到 nums = [12,7,6] 。
 * 现在，nums 中不存在相邻的非互质数。
 * 因此，修改后得到的最终数组是 [12,7,6] 。
 * 注意，存在其他方法可以获得相同的最终数组。
 * 示例 2 ：
 *
 * 输入：nums = [2,2,1,1,3,3,3]
 * 输出：[2,1,1,3]
 * 解释：
 * - (3, 3) 是一组非互质数，且 LCM(3, 3) = 3 。得到 nums = [2,2,1,1,3,3] 。
 * - (3, 3) 是一组非互质数，且 LCM(3, 3) = 3 。得到 nums = [2,2,1,1,3] 。
 * - (2, 2) 是一组非互质数，且 LCM(2, 2) = 2 。得到 nums = [2,1,1,3] 。
 * 现在，nums 中不存在相邻的非互质数。
 * 因此，修改后得到的最终数组是 [2,1,1,3] 。
 * 注意，存在其他方法可以获得相同的最终数组。
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 105
 * 1 <= nums[i] <= 105
 * 生成的测试用例可以保证最终数组中的值 小于或者等于 108 。
 */
public class LC6019 {
    public static void main(String[] args) {
        //int[] nums = {6,4,3,2,7,6,2};
        //int[] nums = {2,2,1,1,3,3,3};
        //int[] nums = {31,97561,97561,97561,97561,97561,97561,97561,97561};
        int[] nums = {287,41,49,287,899,23,23,20677,5,825};
        System.out.println(new Solution().replaceNonCoprimes(nums));
    }
    static class Solution {
        public List<Integer> replaceNonCoprimes(int[] nums) {
            Stack<Integer> stack = new Stack<>();
            for(int num : nums){
                while (!stack.isEmpty() && gcd(stack.peek(),num)>1){
                    // 循环相邻的2个数是非互质数，做化简
                    int x = stack.pop();
                    num = lcm(x,num);
                }
                stack.push(num);
            }
            return new ArrayList<>(stack);
        }
        // 最大公约数
        public int gcd(int a, int b) {
            if (b == 0) return a;
            return gcd(b,  a % b);
        }
        // 最小公倍数
        public int lcm(int a,int b){
            return (int) (((long)a * (long)b) / (long)gcd(a,b));
        }
    }
}
/**
 * 2022-03-06
 * 基础知识点：
 *  最大公约数 和 最小公倍数的计算
 *
 * 思路：
 * 利用栈做相邻2个数a,b之前的化简：
 *  1. 如果ab是非互质数，则将栈顶数字出栈，2数的最小公倍数压入栈中（循环栈中数字）
 *  2. 如果ab不是非互质数，则直接将b压入栈中
 *  3. 最后将栈里的数字转list返回
 */
